Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining the privacy of both x and y. Efficient SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. For example, SFE algorithms have been employed in auctions, contract signing and distributed database mining applications. As computation and communication resources have increased, SFE has become truly practical for common use. A malicious SFE model provides a guarantee of complete privacy of the players' inputs, even when a dishonest player follows an arbitrary cheating strategy.
Existing generic two-party SFE algorithms typically employ Garbled Circuits (GCs). For a detailed discussion of GCs, see, for example, Y. Lindell and B. Pinkas, “A Proof of Yao's Protocol for Secure Two-Party Computation,” Journal of Cryptology, 22(2):161-188 (2009). For reasonably complex functions, however, the data transfer required for SFE is prohibitive. In fact, the communication complexity of GC-based SFE protocols is dominated by the size of the GC, which can reach Megabytes or Gigabytes even for relatively small and simple functions (e.g., the GC for a single secure evaluation of the block cipher AES has size 0.5 Megabytes).
While transmission of large amounts of data is often possible, existing networks will not scale, should SFE be widely deployed. This is particularly true for wireless networks, or for larger scale deployment of secure computations, e.g., by banks or service providers, with a large number of customers. Additional obstacles include energy consumption required to transmit/receive the data, and the resulting reduced battery life in mobile clients, such as smartphones. Computational load on the server is also a significant problem. Moreover, security against more powerful malicious adversaries requires the use of the standard cut-and-choose technique, which in turn requires transfer of multiple GCs.
Thus, a number of techniques have been proposed or suggested to employ a hardware token at the client to improve the communication efficiency of Yao's garbled circuit generation. See, e.g., K. Jaarvinen et al. “Embedded SFE: Offloading Server and Network Using Hardware Tokens,” Financial Cryptography and Data Security, FC 2010, incorporated by reference herein in its entirety. The token allows much of the data to be generated locally by the client, avoiding much of the data transfer (a few Kilobytes, for example, may still be needed). The existing token-based techniques for Yao's garbled circuit generation, however, assume complete tamper-resistance of the hardware token. These techniques may not remain secure if the attacker gains even a few bits of information about the internal state of the token, using side-channel techniques, such as differential power analysis or an analysis of electro-magnetic radiation.
U.S. patent application Ser. No. 13/173,612, filed Jun. 30, 2011, entitled “Garbled Circuit Generation in a Leakage-Resilient Manner,” (now U.S. Pat. No. 8,881,295), incorporated by reference herein in its entirety, discloses garbled circuit generation techniques for generic two-party SFE algorithms that do not require complete tamper-resistance of the hardware token. While the disclosed garbled circuit generation techniques provide secure generation of GCs, even in the presence of continual, adaptive information leakage during execution of the token, they require the use of a token having significant memory capacity to store a garbled circuit. A need therefore remains for secure garbled circuit generation techniques having a reduced storage requirement.